package beusoft.ccjk.com.calculator.sort;

/**
 * Created by CCJK on 2017/12/16.
 * 背包问题
 * 目标：从所有物品中找到其中几个，使得他们的重量之和为背包的负重
 */
public class Pack {

    private int mTarget;//背包的负重
    int mArray[];//所有物品的重量的数组


    public static void main(String[] args) {
        int arr[] = {7, 9, 3, 5, 1, 6, 81, 8, 5};
        new Pack(33, arr).tryFind();
    }

    public Pack(int target, int[] arr) {
        this.mTarget = target;
        this.mArray = arr;
    }

    public void tryFind() {

        try {

            find(mArray, mTarget);
        } catch (Exception e) {
        }

    }

    private int[] find(int[] arr, int target) throws Exception {
        dumps(arr, target);
        for (int i = 0; i < arr.length; i++) {
            int item = arr[i];
            if (item < target) {
                if (i == arr.length - 1) {
                    //  dumps(arr, target);
                    println("查找失败");
                } else {
                    int subArr[] = getSubArr(i + 1, arr);
                    int result[] = find(subArr, target - item);
                    if (result == null) {
                        // dumps(arr, target);
                        println("查找失败");
                    } else {
                        //  dumps(arr, target);
                        println("查找成功");
                        for (int j = 0; j < result.length; j++) {
                            print(" ," + result[j]);
                        }
                        //测试
                        return null;
                    }
                }
            } else if (item > target) {
                int subArr[] = getSubArr(i + 1, arr);
                int result[] = find(subArr, target);
                if (result == null) {
                    // dumps(arr, target);
                    println("查找失败");
                } else {
                    //  dumps(arr, target);
                    println("查找成功");
                    for (int j = 0; j < result.length; j++) {
                        print(" ," + result[j]);
                    }
                    //测试
                    return null;
                }
            } else {

                println("查找成功");
                throw new Exception("");
            }
        }
        return null;
    }

    private int[] getSubArr(int start, int[] arr) {
        int subArr[] = new int[arr.length - start];
        for (int i = start; i < arr.length; i++) {
            subArr[i - start] = arr[i];
        }
        return subArr;
    }

    private void dumps(int arr[], int target) {
        println("");
        println("////////////////////");
        print("从{ ");
        for (int i = 0; i < arr.length; i++) {
            print(" ," + arr[i]);
        }
        print(" }找" + target);
        println("");
    }

    private void println(Object o) {
        System.out.println(o);
    }

    private void print(Object o) {
        System.out.print(o);
    }

}
